/*
 * @lc app=leetcode.cn id=160 lang=cpp
 *
 * [160] 相交链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        //找到两个链表相交的节点位置
        ListNode *curA = headA;
        ListNode *curB = headB;
        //求长度
        int lenA = 0;
        int lenB = 0;
        while (curA != NULL)
        {
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL)
        {
            lenB++;
            curB = curB->next;
        }
        //现在已经获取两链表长度 比较长度 让长链表先走
        curA = headA;
        curB = headB;
        //保证lenA curA为长的那条
        if (lenB > lenA)
        {
            swap(lenA, lenB);
            swap(curA, curB);
        }
        int larger = lenA - lenB;
        while (larger--)
        {
            curA = curA->next;
        }
        while (curA != NULL)
        {
            if (curA == curB)
            {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};
// @lc code=end
